package com.lnn.algorithm.aco;

import lombok.Data;

import java.util.Random;
import java.util.Vector;

/**
 * 蚂蚁实体类
 *
 * @author: Li Ning Ning
 * @time: 2021/7/23 16:21
 * @description: TODO
 * @version: 1.0
 */
@Data
public class Ant {

    /**
     * 已搜索过的城市
     */
    private Vector<Integer> tabu;

    /**
     * 尚未搜索的城市
     */
    private Vector<Integer> allowedCities;

    /**
     * 信息素变化矩阵
     */
    private double[][] delta;

    /**
     * 城市间距离矩阵
     */
    private int[][] distance;

    /**
     * 信息素重要程度因子
     */
    private double alpha;

    /**
     * 启发函数重要程度因子
     */
    private double beta;

    /**
     * 路径长度
     */
    private int tourLength;

    /**
     * 城市数量
     */
    private int cityNum;

    /**
     * 起始城市
     */
    private int firstCity;

    /**
     * 当前城市
     */
    private int currentCity;

    /**
     * 取随机数
     */
    private Random random;

    public Ant() {
    }

    public Ant(int num) {
        cityNum = num;
        tourLength = 0;
    }

    /**
     * 初始化蚂蚁，随机选择起始位置
     *
     * @param distance 距离矩阵
     * @param alpha    信息素重要程度因子
     * @param beta     启发函数重要程度因子
     */
    public void init(int[][] distance, double alpha, double beta) {
        this.alpha = alpha;
        this.beta = beta;
        this.allowedCities = new Vector<>();
        this.tabu = new Vector<>();
        this.distance = distance;
        this.delta = new double[cityNum][cityNum];
        this.random = new Random(System.currentTimeMillis());
        // 初始化数据成员
        for (int i = 0; i < cityNum; i++) {
            allowedCities.add(i);
            for (int j = 0; j < cityNum; j++) {
                delta[i][j] = 0.f;
            }
        }
        // 随机选择第一个城市位置
        this.firstCity = random.nextInt(cityNum);
        for (int i : allowedCities) {
            if (i == firstCity) {
                allowedCities.remove(i);
                break;
            }
        }

        tabu.add(firstCity);
        currentCity = firstCity;
    }

    /**
     * 选择下一个城市,根据信息素
     *
     * @param pheromone 信息素矩阵
     */
    public void selectNextCity(double[][] pheromone) {
        double[] p = new double[cityNum];
        double sum = 0;
        // 计算分母部分
        for (int i : allowedCities) {
            sum += Math.pow(pheromone[currentCity][i], alpha)
                    * Math.pow(1.0 / distance[currentCity][i], beta);
        }
        // 计算概率矩阵
        for (int i = 0; i < cityNum; i++) {
            boolean flag = false;
            for (int j : allowedCities) {
                if (i == j) {
                    p[i] = (Math.pow(pheromone[currentCity][i], alpha) * Math
                            .pow(1.0 / distance[currentCity][i], beta))
                            / sum;
                    flag = true;
                    break;
                }
            }
            if (!flag) {
                p[i] = 0.0;
            }
        }

        // 采用轮盘赌选择下一个城市
        double selectP = random.nextDouble();
        int selectCity = 0;
        double sum1 = 0.f;
        for (int i = 0; i < cityNum; i++) {
            sum1 += p[i];
            if (sum1 >= selectP) {
                selectCity = i;
                break;
            }
        }

        // 从允许选择的城市中去除select city
        for (Integer i : allowedCities) {
            if (i == selectCity) {
                allowedCities.remove(i);
                break;
            }
        }

        // 在已搜索过的城市表中添加select city
        tabu.add(selectCity);
        // 将当前城市改为选择的城市
        currentCity = selectCity;
    }

    /**
     * 计算当前蚂蚁路径长度
     *
     * @return 路径长度
     */
    private int calculateTourLength() {
        int len = 0;
        for (int i = 0; i < cityNum; i++) {
            len += distance[this.tabu.get(i)][this.tabu.get(i + 1)];
        }
        return len;
    }

    public int getTourLength() {
        return calculateTourLength();
    }

}
